#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 5 + 1e6;
const int maxn = 5 + 3e5;

int tot;
struct Node {
    int to;
    Node *nex;
} pool[max_size << 1], *head[maxn];
inline void add(int l, int r) {
    pool[++tot] = {r, head[l]};
    head[l] = pool + tot;
}

int n, m;
bool visit[maxn];

inline void init() {
    tot = 0;
    memset(head, 0, sizeof(Node *) * (n + 5));
    memset(visit, 0, sizeof(bool) * (n + 5));
    visit[0] = 1;
}

void dfs(int u, int &vertex, int &edg) {
    visit[u] = 1, vertex++; // 顶点计数
    for (auto now = head[u]; now; now = now->nex) {
        int v = now->to;
        edg++; // 边计数
        if (visit[v]) continue;
        dfs(v, vertex, edg);
    }
}

int main() {
    int Q = rad();
    rf(q, Q) {
        n = rad(), m = rad();
        init();
        rf(i, m) {
            int l = rad(), r = rad();
            add(l, r), add(r, l);
        }

        int ans = 0;
        rf(i, n) {
            if (!visit[i]) {
                int vertex = 0, edg = 0;
                dfs(i, vertex, edg);
                ans += max(0, edg / 2 - vertex);
            }
        }
        printf("Case #%d: %d\n", q, ans);
    }
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}

/*
1
6 5
1 2
1 3
4 5
4 6
5 6

*/